﻿#region

using System;
using System.Collections.Generic;
using System.Linq;

#endregion

namespace Domain.Algorithms {
    public class TriangulatedGraphUtils {
        public static bool IsGraphTriangulated(Graph<HyperEdge> graph) {
            var vertexedGraph = new Graph<HyperEdge>(graph);
            var hasChanged = true;
            while (hasChanged) {
                hasChanged = false;

                for (var i = 0; i < vertexedGraph.Vertices.Count; i++) {
                    var v = vertexedGraph.Vertices[i];
                    if (IsSimplicial(vertexedGraph, v)) {
                        vertexedGraph.Remove(v);
                        hasChanged = true;
                        break;
                    }
                }
            }

            return vertexedGraph.IsEmpty;
        }

        private static bool IsSimplicial(Graph<HyperEdge> graph, Vertex vertex) {
            var neighbourhood = GraphUtils<HyperEdge>.Neighbourhood(graph, vertex);
            if (neighbourhood.Count == 0 || neighbourhood.Count == 1) {
                return true;
            }

            for (var i = 0; i < neighbourhood.Count - 1; i++) {
                for (var j = i + 1; j < neighbourhood.Count; j++) {
                    var vertex1 = neighbourhood[i];
                    var vertex2 = neighbourhood[j];
                    var x = false;
                    foreach (var edge in graph.Edges) {
                        if (edge.Vertices.Contains(vertex1) && edge.Vertices.Contains(vertex2)) {
                            x = true;
                        }
                    }
                    if (x == false) {
                        return false;
                    }
                }
            }
            return true;
        }

        public static List<Vertex> FindPerfectEliminationOrdering(Graph<HyperEdge> graph) {
            /* http://en.wikipedia.org/wiki/Lexicographic_breadth-first_search#The_algorithm */
            var subgraph = new Graph<HyperEdge>(graph);

            /*Initialize a sequence Σ of sets, to contain a single set containing all vertices.*/
            var sequenceOfSets = new List<List<Vertex>>();
            var temp = new Vertex[graph.NumberVertices];
            graph.Vertices.CopyTo(temp);
            sequenceOfSets.Add(temp.ToList());

            /*Initialize the output sequence of vertices to be empty*/
            var outputSequence = new List<Vertex>();

            /*While Σ is non-empty:*/
            while (sequenceOfSets.Count != 0) {
                /*Find and remove a vertex v from the first set in Σ*/
                var v = sequenceOfSets[0].Where(vertex => IsSimplicial(subgraph, vertex)).First();
                /*If the first set in Σ is now empty, remove it from Σ*/
                sequenceOfSets[0].Remove(v);
                subgraph.Remove(v);
                if (sequenceOfSets[0].Count == 0) {
                    sequenceOfSets.RemoveAt(0);
                }
                /*Add v to the end of the output sequence.*/
                outputSequence.Add(v);
                /*For each edge v-w such that w still belongs to a set S in Σ:*/
                var neighbourhood = GraphUtils<HyperEdge>.Neighbourhood(graph, v);
                var newSequenceOfSets = new List<List<Vertex>>();
                foreach (var set in sequenceOfSets) {
                    var neighbours = new List<Vertex>();
                    var nonNeighbours = new List<Vertex>();
                    foreach (var w in set) {
                        if (neighbourhood.Contains(w)) {
                            neighbours.Add(w);
                        }
                        else {
                            nonNeighbours.Add(w);
                        }
                    }
                    if (neighbours.Count != 0) {
                        newSequenceOfSets.Add(neighbours);
                    }
                    if (nonNeighbours.Count != 0) {
                        newSequenceOfSets.Add(nonNeighbours);
                    }
                }
                sequenceOfSets = newSequenceOfSets;
            }
            return outputSequence;
        }

        public static List<List<Vertex>> FindAllMaximumCliques(Graph<HyperEdge> graph) {
            var cliqueCandidates = FindMaximumCliqueCandidates(graph);
            var maxCliqueSize = 0;
            foreach (var cliqueCandidate in cliqueCandidates) {
                if (cliqueCandidate.Count < maxCliqueSize) {
                    continue;
                }
                maxCliqueSize = cliqueCandidate.Count;
            }
            return cliqueCandidates.Where(cc => cc.Count == maxCliqueSize).ToList();
        }

        private static List<List<Vertex>> FindMaximumCliqueCandidates(Graph<HyperEdge> graph) {
            var perfectEliminationOrdering = FindPerfectEliminationOrdering(graph);

            var cliqueCandidates = new List<List<Vertex>>();

            for (var i = 0; i < perfectEliminationOrdering.Count; i++) {
                var v = perfectEliminationOrdering[i];
                var neighbourhood = GraphUtils<HyperEdge>.Neighbourhood(graph, v);
                var cliqueCandidate = new List<Vertex>();
                cliqueCandidates.Add(cliqueCandidate);
                cliqueCandidate.Add(v);
                for (var j = i + 1; j < perfectEliminationOrdering.Count; j++) {
                    var w = perfectEliminationOrdering[j];
                    if (neighbourhood.Contains(w)) {
                        cliqueCandidate.Add(w);
                    }
                }
            }
            return cliqueCandidates;
        }

        public static void TriangulateGraph(ref Graph<HyperEdge> givenGraph) {
            Dictionary<Vertex, Vertex> d;
            var graph = new Graph<HyperEdge>(givenGraph, out d);
            var dInverted = d.ToDictionary(pair => pair.Value, pair => pair.Key);

            while (graph.NumberVertices > 0) {
                var leastDegreeVertex = LeastDegreeVertex(graph);

                List<HyperEdge> edges = FindEdgesToCompleteNeighbourhoodToClique(graph, leastDegreeVertex);

                foreach (var edge in edges) {
                    graph.AddEdge(edge);
                    givenGraph.AddEdge(new HyperEdge(edge.Vertices.Select(v => dInverted[v]).ToArray()));
                }

                graph.Remove(leastDegreeVertex);
            }
        }

        private static List<HyperEdge> FindEdgesToCompleteNeighbourhoodToClique(Graph<HyperEdge> graph, Vertex vertex) {
            var edges = new List<HyperEdge>();

            var neighbourhood = GraphUtils<HyperEdge>.Neighbourhood(graph, vertex);

            for (var i = 0; i < neighbourhood.Count - 1; i++)
            {
                for (var j = i + 1; j < neighbourhood.Count; j++)
                {
                    var vertex1 = neighbourhood[i];
                    var vertex2 = neighbourhood[j];
                    var needToAddThisEdgeToList = true;
                    foreach (var edge in graph.Edges)
                    {
                        if (edge.Vertices.Contains(vertex1) && edge.Vertices.Contains(vertex2))
                        {
                            needToAddThisEdgeToList = false;
                            break;
                        }
                    }
                    if (needToAddThisEdgeToList)
                    {
                        edges.Add(new HyperEdge(vertex1, vertex2));
                    }
                }
            }

            return edges;
        }

        private static Vertex LeastDegreeVertex(Graph<HyperEdge> graph) {
            var degrees = graph.Vertices.ToDictionary(vertex => vertex, vertex => 0);

            foreach (var edge in graph.Edges) {
                foreach (var vertex in edge.Vertices) {
                    degrees[vertex]++;
                }
            }
            var min = degrees.Values.Min();
            return degrees.Where(pair => pair.Value == min).Last().Key;
        }
    }
}